package cn.edu.xjtu.competiton.lccp;

/**
 * @author Hydrion-QLz
 * @date 2022-04-16 15:07
 * @description
 */
public class Second {
    public static void main(String[] args) {
        Second solution = new Second();
        int[] meterials = {3, 2, 4, 1, 2};
        int[][] cookbooks = {{1, 1, 0, 1, 2}, {2, 1, 4, 0, 0}, {3, 2, 4, 1, 0}};
        int[][] attr = {{3, 2}, {2, 4}, {7, 6}};
        int limit = 5;
        System.out.println(solution.perfectMenu(meterials, cookbooks, attr, limit));
    }

    int satisfy = 0;
    int full = 0;
    int ans = 0;

    public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {
        backtrack(materials, cookbooks, attribute, limit, 0);
        if (ans == 0) {
            return -1;
        }
        return ans;
    }

    private void backtrack(int[] materials, int[][] cookbooks, int[][] attribute, int limit, int index) {
        if (full >= limit) {
            ans = Math.max(ans, satisfy);
        }
        for (int i = index; i < cookbooks.length; i++) {
            if (bound(materials, cookbooks, i)) {
                for (int j = 0; j < materials.length; j++) {
                    materials[j] -= cookbooks[i][j];
                }
                satisfy += attribute[i][0];
                full += attribute[i][1];
                backtrack(materials, cookbooks, attribute, limit, i + 1);
                satisfy -= attribute[i][0];
                full -= attribute[i][1];
                for (int j = 0; j < materials.length; j++) {
                    materials[j] += cookbooks[i][j];
                }
            }
        }

    }

    private boolean bound(int[] materials, int[][] cookbooks, int i) {
        for (int j = 0; j < materials.length; j++) {
            if (materials[j] < cookbooks[i][j]) return false;
        }
        return true;
    }
}
